use rand::random;

/// quickly calculate (a ^ p) % mo
fn qpow(mut a: u128, mut p: u128, mo: u128) -> u128 {
    let mut res = 1;
    while p > 0 {
        if (p & 1) == 1 {
            res = res * a % mo;
        }
        a = a * a % mo;
        p >>= 1;
    }
    res
}

/// use Miller-Rabin test
fn is_prime(n: u128) -> bool {
    if n < 3 || (n & 1) == 0 {
        return n == 2;
    }
    if n % 3 == 0 {
        return n == 3;
    }
    let (mut u, mut t) = (n - 1, 0);
    while (u & 1) == 0 {
        u /= 2;
        t += 1;
    }
    // check 10 times
    for _ in 0..10 {
        let a = random::<u128>() % (n - 3) + 2;
        let mut v = qpow(a, u, n);
        if v == 1 {
            continue;
        }
        let mut s = 0;
        for _ in 0..t {
            if v == n - 1 {
                break;
            }
            v = v * v % n;
            s += 1;
        }
        if s == t {
            return false;
        }
    }
    true
}

pub fn min_edge_prime_num(number: u32) -> String {
    let number = number as f64;
    let (mut cnt, mut long) = (0u128, 1u128);
    let (mut now, mut step, mut total) = (1u128, 0u128, 1u128);
    // calculate every square
    loop {
        step += 2;
        for _ in 0..4 {
            now += step;
            // now is a number in diagonal
            if is_prime(now) {
                cnt += 1;
            }
        }
        total += 4;
        long += 2;
        if (cnt as f64 * 100.0 / total as f64) < number {
            break;
        }
    }
    format!("{},{}", long, cnt)
}
